Lowest Common Ancestor Code
Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.
#include <iostream> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; class Node { public: Node() { } vector<Node *> children; Node *parent; }; Node *make_random_tree(size_t size,Node *root=NULL) { if(root == NULL) { root = new Node(); } Node *current = root; size_t children=rand()%size; for(size_t i=0;i<children;i++) { Node *nd = new Node(); nd->parent = current; current->children.push_back(nd); } for(size_t n=0;n<current->children.size();n++) { make_random_tree(size-children,current->children[n]); } return root; } Node *get_random(Node *root,size_t avg_size) { Node *current = root; for(;rand()%(avg_size*2) != 0;) { if(current->children.size() == 0) return current; current = current->children[rand()%current->children.size()]; } return current; } Node * get_next_child(Node *node,Node *child) { bool next=false; for(size_t n=0;n<node->children.size();n++) { if(next==true) { return node->children[n]; } if(node->children[n] == child) next=true; } return NULL; } vector<Node *> get_path(Node *root,Node *n) { vector<Node *> current_path; current_path.push_back(root); if(n==root) return current_path; Node *current_child = root->children[0]; for(;;) { current_path.push_back(current_child); if(current_child == n) return current_path; if(current_child->children.size() != 0) { current_path.push_back(current_child->children[0]); current_child = current_child->children[0]; } else { current_child = NULL; for(;current_child == NULL;) { Node *old_child = current_path[current_path.size()-1]; current_path.erase(current_path.begin()+current_path.size()-1,current_path.end()); current_child = get_next_child(current_path[current_path.size()-1],old_child); if(old_child==root) { return vector<Node *>(); } } } } // Should never get here return vector<Node *>(); } vector<Node *> get_path_parent(Node *root,Node *n) { vector<Node *> v; for(Node *current = n;current != root;current = current->parent) { v.push_back(current); } v.push_back(root); reverse(v.begin(),v.end()); return v; } Node *find_lca_parent(Node *root,Node *n1,Node *n2) { vector<Node *> path1 = get_path_parent(root,n1); vector<Node *> path2 = get_path_parent(root,n2); for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl; for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl; size_t shortest_path_length; if(path1.size() < path2.size()) shortest_path_length = path1.size(); else shortest_path_length = path2.size(); size_t n; for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++); return path1[n-1]; } Node *find_lca(Node *root,Node *n1,Node *n2) { vector<Node *> path1 = get_path(root,n1); vector<Node *> path2 = get_path(root,n2); size_t shortest_path_length; if(path1.size() < path2.size()) shortest_path_length = path1.size(); else shortest_path_length = path2.size(); size_t n; for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++); return path1[n-1]; } int main() { Node *root = make_random_tree(100); Node *n1 = get_random(root,20); Node *n2 = get_random(root,20); Node *lca1a = find_lca_parent(root,n1,n2); Node *lca1b = find_lca (root,n1,n2); cout << "LCA1-a: " << lca1a << endl; cout << "LCA1-b: " << lca1a << endl; Node *n3 = root->children[0]->children[0]->children[0]; Node *n4 = root->children[0]->children[0]->children[1]; Node *lca2a = find_lca_parent(root,n3,n4); Node *lca2b = find_lca (root,n3,n4); cout << "LCA2-a: " << lca2a << endl; cout << "LCA2-b: " << lca2b << endl; }